package acm.蓝桥杯1;

import java.util.Scanner;

public class 方程 {
    public static final int MOD = 1000000007;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int count = sc.nextInt();
        while (count-- > 0) {
            int n = sc.nextInt();
            int k = sc.nextInt();
            int[] keys = keys(k);
            long res = result(keys[0], n);
            System.out.println(res);
        }
    }

    public static int[] keys(int k) {
        int[] res = new int[2];
        res[0] = (int) ((k + Math.sqrt(k * k - 4)) / 2);
        res[1] = (int) ((k - Math.sqrt(k * k - 4)) / 2);
        return res;
    }

    public static long result(int x, int n) {
        long x_n = 1;
        while (n > 0) {
            if (n % 2 == 1) {
                x_n = (x_n * x) % MOD;
            }
            x = (x * x) % MOD;
            n /= 2;
        }
        return x_n+1/x_n;
    }
}
